{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Make Array Strictly Increasing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makeArrayIncreasing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组严格递增"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数数组&nbsp;<code>arr1</code> 和 <code>arr2</code>，返回使&nbsp;<code>arr1</code>&nbsp;严格递增所需要的最小「操作」数（可能为 0）。</p>\n",
    "\n",
    "<p>每一步「操作」中，你可以分别从 <code>arr1</code> 和 <code>arr2</code> 中各选出一个索引，分别为&nbsp;<code>i</code> 和&nbsp;<code>j</code>，<code>0 &lt;=&nbsp;i &lt; arr1.length</code>&nbsp;和&nbsp;<code>0 &lt;= j &lt; arr2.length</code>，然后进行赋值运算&nbsp;<code>arr1[i] = arr2[j]</code>。</p>\n",
    "\n",
    "<p>如果无法让&nbsp;<code>arr1</code>&nbsp;严格递增，请返回&nbsp;<code>-1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>用 2 来替换 <code>5，之后</code> <code>arr1 = [1, 2, 3, 6, 7]</code>。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr1 = [1,5,3,6,7], arr2 = [4,3,1]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>用 3 来替换 <code>5，然后</code>用 4 来替换 3<code>，得到</code> <code>arr1 = [1, 3, 4, 6, 7]</code>。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>无法使 <code>arr1 严格递增</code>。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr1.length, arr2.length &lt;= 2000</code></li>\n",
    "\t<li><code>0 &lt;= arr1[i], arr2[i] &lt;= 10^9</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [make-array-strictly-increasing](https://leetcode.cn/problems/make-array-strictly-increasing/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [make-array-strictly-increasing](https://leetcode.cn/problems/make-array-strictly-increasing/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,3,6,7]\\n[1,3,2,4]', '[1,5,3,6,7]\\n[4,3,1]', '[1,5,3,6,7]\\n[1,6,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        def erfen(target):\n",
    "            left, right = 0, len(arr2)-1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if arr2[mid] >= target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "        \n",
    "        arr2 = sorted(set(arr2))\n",
    "        arr1 = [-1] + arr1 + [float('inf')]\n",
    "        n = len(arr1)\n",
    "        dp = [float('inf') for _ in range(n)]\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n):\n",
    "            index = erfen(arr1[i])\n",
    "            # print(index)\n",
    "            for k in range(1, min(i-1, index)+1):\n",
    "                if arr1[i-k-1] < arr2[index-k]:\n",
    "                    dp[i] = min(dp[i], dp[i-k-1]+k)\n",
    "            if arr1[i] > arr1[i-1]:\n",
    "                dp[i] = min(dp[i], dp[i-1])\n",
    "        \n",
    "        return dp[-1] if dp[-1] != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "inf = 1 << 30\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(set(arr2))\n",
    "        arr1.insert(0, -1)\n",
    "        arr1.append(inf)\n",
    "\n",
    "        n = len(arr1)\n",
    "        dp = [inf] * n\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n):\n",
    "            # 能换多少个\n",
    "            idx = bisect_left(arr2, arr1[i])\n",
    "            for k in range(1, min(i, idx+1)):\n",
    "                if arr1[i-k-1] < arr2[idx-k]:\n",
    "                    dp[i] = min(dp[i], dp[i-k-1] + k)\n",
    "            # 不换\n",
    "            if arr1[i-1] < arr1[i]:\n",
    "                dp[i] = min(dp[i], dp[i-1])\n",
    "        \n",
    "        return dp[-1] if dp[-1] < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = list(set(arr2))\n",
    "        arr2.sort()\n",
    "        arr1 = [-1] + arr1 + [float('inf')]\n",
    "\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        max_num = min(m, n)\n",
    "        dp = [float('inf')] * m\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(1, m):\n",
    "            if arr1[i] > arr1[i - 1]:\n",
    "                dp[i] = min(dp[i], dp[i - 1])\n",
    "            k = bisect.bisect_left(arr2, arr1[i])\n",
    "            for j in range(1, min(max_num, i - 1, k) + 1):\n",
    "                if arr2[k - j] > arr1[i - j - 1]:\n",
    "                    dp[i] = min(dp[i], dp[i - j - 1] + j)\n",
    "        return dp[-1] if dp[-1] <= max_num else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        a = arr1 + [inf]\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(a)\n",
    "        f = [0] * n\n",
    "        for i, x in enumerate(a):\n",
    "            k = bisect_left(arr2, x)\n",
    "            ans = 0 if k >= i else -inf \n",
    "            if i and a[i - 1] < x:\n",
    "                ans = max(ans, f[i - 1])\n",
    "            for j in range(i - 2, max(i - k - 2, -1), -1):\n",
    "                if arr2[k - (i - j - 1)] > a[j]:\n",
    "                    ans = max(ans, f[j])\n",
    "\n",
    "            f[i] = ans + 1\n",
    "        return -1 if f[-1] < 0 else n - f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr1 = [-inf] + arr1 + [inf]\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr1)\n",
    "\n",
    "        f = [0] + [inf] * (n - 1)\n",
    "        for i, x in enumerate(arr1[1:], 1):\n",
    "            j = bisect_left(arr2, x)\n",
    "            for k in range(1, min(i - 1, j) + 1):\n",
    "                if arr1[i - k - 1] < arr2[j - k]:\n",
    "                    f[i] = min(f[i], f[i - k - 1] + k)\n",
    "            if arr1[i - 1] < arr1[i]:\n",
    "                f[i] = min(f[i], f[i - 1])\n",
    "        return f[-1] if f[-1] < inf else -1\n",
    "\n",
    "        # b.sort()\n",
    "        # @cache\n",
    "        # def dfs(i, pre):\n",
    "        #     if i < 0:\n",
    "        #         return 0\n",
    "        #     res = dfs(i - 1, a[i]) if a[i] < pre else inf\n",
    "        #     k = bisect_left(b, pre) - 1\n",
    "        #     if k >= 0:\n",
    "        #         res = min(res, dfs(i - 1, b[k]) + 1)\n",
    "        #     return res\n",
    "        # res = dfs(len(a) - 1, inf)\n",
    "        # return res if res < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr2)\n",
    "        rep = [inf] * n\n",
    "        keep = 0\n",
    "        for i, x in enumerate(arr1):\n",
    "            pre = arr1[i-1] if i > 0 else -1\n",
    "            tmp_rep = [inf] * n\n",
    "            tmp_keep = inf\n",
    "            # 换\n",
    "            idx = bisect_left(arr2, pre+1)\n",
    "            for j in range(idx, n):\n",
    "                tmp_rep[j] = keep + 1\n",
    "            mn = inf\n",
    "            for j in range(1, n):\n",
    "                mn = min(mn, rep[j-1] + 1)\n",
    "                tmp_rep[j] = min(tmp_rep[j], mn)\n",
    "            # 不换\n",
    "            if x > pre:\n",
    "                tmp_keep = keep\n",
    "            idx = bisect_left(arr2, x)\n",
    "            for j in range(idx):\n",
    "                tmp_keep = min(tmp_keep, rep[j])\n",
    "            \n",
    "            rep = tmp_rep\n",
    "            keep = tmp_keep\n",
    "        \n",
    "        res = min(keep, min(rep))\n",
    "        return res if res < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = set(arr2)\n",
    "        arr2 = list(arr2)\n",
    "        arr2.sort()\n",
    "        record = [-1] * (len(arr2) + 1)\n",
    "        record[0] = arr1[0]\n",
    "        if arr2[0] < arr1[0]:\n",
    "            record[1] = arr2[0]\n",
    "        #print(arr2)\n",
    "        #print(record)\n",
    "        for i in range(1, len(arr1)):\n",
    "            record2 = [-1] * (len(arr2) + 1)\n",
    "            s = len(arr2) - 1\n",
    "            for j in range(len(record)):\n",
    "                if record[j] != -1:\n",
    "                    if arr1[i] > record[j]:\n",
    "                        if record2[j] == -1 or record2[j] > arr1[i]:\n",
    "                            record2[j] = arr1[i]\n",
    "                    while s > 0 and arr2[s - 1] > record[j]:\n",
    "                        s -= 1\n",
    "                    if arr2[s] > record[j]:\n",
    "                        if record2[j + 1] == -1 or record2[j + 1] > arr2[s]:\n",
    "                            record2[j + 1] = arr2[s]\n",
    "            #print(i)\n",
    "            #print(record)\n",
    "            #print(record2)\n",
    "            record = record2\n",
    "        for i in range(len(record2)):\n",
    "            if record2[i] != -1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        maxv = 1000000000\n",
    "        arr1 = [-1] + arr1 + [maxv + 5]\n",
    "        arr2 = sorted(list(set(arr2)))\n",
    "        n = len(arr1)\n",
    "        dp = [0] + [maxv]*(n-1)\n",
    "        for i in range(1,n):\n",
    "            j = bisect_left(arr2, arr1[i])\n",
    "            for k in range(1, min(i-1, j) + 1):  \n",
    "                if arr1[i-k-1] < arr2[j-k]:\n",
    "                    dp[i] = min(dp[i], dp[i-k-1] + k)\n",
    "            if arr1[i-1] < arr1[i]:          \n",
    "                dp[i] = min(dp[i], dp[i-1])\n",
    "        return dp[-1] if dp[-1] < maxv else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        a = arr1 + [inf]\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(a)\n",
    "        f = [0] * n\n",
    "        for i, x in enumerate(a):\n",
    "            k = bisect_left(arr2, x)\n",
    "            ans = 0 if k >= i else -inf \n",
    "            if i and a[i - 1] < x:\n",
    "                ans = max(ans, f[i - 1])\n",
    "            for j in range(i - 2, max(i - k - 2, -1), -1):\n",
    "                if arr2[k - (i - j - 1)] > a[j]:\n",
    "                    ans = max(ans, f[j])\n",
    "\n",
    "            f[i] = ans + 1\n",
    "        return -1 if f[-1] < 0 else n - f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr1 = arr1 + [float('inf')]\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n1 = len(arr1)\n",
    "        dp = [float('inf')] * n1\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n1):\n",
    "            if arr1[i] > arr1[i - 1]:\n",
    "                dp[i] = dp[i - 1]\n",
    "            idx = bisect.bisect_left(arr2, arr1[i])\n",
    "            for j in range(1, min(idx, i) + 1):\n",
    "                if i == j or arr2[idx - j] > arr1[i - j - 1] :\n",
    "                    dp[i] = min(dp[i], (dp[i - j - 1] if i > j else 0) + j)\n",
    "        return dp[-1] if dp[-1] != float('inf') else - 1\n",
    "\n",
    "\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        m = len(arr1)\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr2)\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[n] = 0\n",
    "        for i, x in enumerate(arr1):\n",
    "            pre = arr1[i-1] if i > 0 else -1\n",
    "            tmp = [inf] * (n + 1)\n",
    "            # 换\n",
    "            for j, y in enumerate(arr2):\n",
    "                if y > pre:\n",
    "                    tmp[j] = dp[n] + 1\n",
    "            mn = inf\n",
    "            for j in range(1, n):\n",
    "                mn = min(mn, dp[j-1] + 1)\n",
    "                tmp[j] = min(tmp[j], mn)\n",
    "            # 不换\n",
    "            if x > pre:\n",
    "                tmp[n] = dp[n]\n",
    "            for j, y in enumerate(arr2):\n",
    "                if x > y:\n",
    "                    tmp[n] = min(tmp[n], dp[j])\n",
    "            dp = tmp\n",
    "        \n",
    "        res = min(dp)\n",
    "        return res if res < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        a = arr1 + [inf]\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(a)\n",
    "        f = [0] * n\n",
    "        for i, x in enumerate(a):\n",
    "            k = bisect_left(arr2, x)\n",
    "            ans = 0 if k >= i else -inf \n",
    "            if i and a[i - 1] < x:\n",
    "                ans = max(ans, f[i - 1])\n",
    "            for j in range(i - 2, max(i - k - 2, -1), -1):\n",
    "                if arr2[k - (i - j - 1)] > a[j]:\n",
    "                    ans = max(ans, f[j])\n",
    "\n",
    "            f[i] = ans + 1\n",
    "        return -1 if f[-1] < 0 else n - f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        len1 = len(arr1)\n",
    "        len2 = len(arr2)\n",
    "        numlist = list(set(arr1.copy()+arr2.copy()))\n",
    "        numlist.sort()\n",
    "        arr2.sort()\n",
    "        inf = len1+len2\n",
    "        lenn = len(numlist)\n",
    "        numdict = {numlist[i]: i+1 for i in range(lenn)}\n",
    "        dp0 = {}\n",
    "        dp1 = {-1: 0}\n",
    "        for i in range(len1):\n",
    "            dp0 = dp1\n",
    "            dp1 = {}\n",
    "            dp1[arr1[i]] = inf\n",
    "            for item in dp0:\n",
    "                # print(item, dp0[item])\n",
    "                if item < arr1[i]:\n",
    "                    dp1[arr1[i]] = min(dp1[arr1[i]], dp0[item])\n",
    "                idx = bisect_left(arr2, item+1)\n",
    "                if idx >= 0 and idx < len2 and arr2[idx] > item:\n",
    "                    if arr2[idx] not in dp1:\n",
    "                        dp1[arr2[idx]] = inf\n",
    "                    dp1[arr2[idx]] = min(dp1[arr2[idx]], dp0[item]+1)\n",
    "        ans = min(dp1[item] for item in dp1)\n",
    "        if ans == len1+len2:\n",
    "            return -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], b: List[int]) -> int:\n",
    "        # 1. 选或不选\n",
    "        # arr2.sort() # 为能二分查找对arr2排序\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i:int, pre:int) -> int:\n",
    "        #     if i < 0: return 0\n",
    "        #     res = dfs(i - 1 , arr1[i]) if arr1[i] < pre else inf #不替换a[i]\n",
    "        #     k = bisect_left(arr2, pre) - 1 #二分查找b中小于pre的最大数的下标\n",
    "        #     if k >= 0: # a[i]替换成小于pre的最大数\n",
    "        #         res = min(res, dfs(i - 1, arr2[k]) + 1)\n",
    "        #     return res\n",
    "        # ans = dfs(len(arr1) - 1, inf) #假设a[n - 1]右侧有个无穷大的数\n",
    "        # return ans if ans < inf else -1\n",
    "\n",
    "        # 2. 枚举哪个\n",
    "        a = arr1 + [inf] #简化代码逻辑\n",
    "        b = sorted(set(b)) #去重+排序\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            k = bisect_left(b, a[i]) # i=时不会继续递归，返回1\n",
    "            res = 0 if k >= i else -inf # 替换a[i]左侧全部元素\n",
    "            if i and a[i - 1] <a[i]: #无替换\n",
    "                res = max(res, dfs(i - 1))\n",
    "            for j in range(i - 2, max(i - k - 2, -1), -1):\n",
    "                if b[k - (i - j - 1)] > a[j]: # a[j+1]到a[i-1]替换成b[k-(i-j-1)]到b[k-1]\n",
    "                    res = max(res, dfs(j))\n",
    "            return res + 1 # 表示a[i] 不替换\n",
    "        ans = dfs(len(a) - 1)  #注意a已经添加了一个元素\n",
    "        return -1 if ans < 0 else len(a) - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr1 = arr1 + [float('inf')]\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n1 = len(arr1)\n",
    "        dp = [float('inf')] * n1\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n1):\n",
    "            if arr1[i] > arr1[i - 1]:\n",
    "                dp[i] = dp[i - 1]\n",
    "            idx = bisect.bisect_left(arr2, arr1[i])\n",
    "            for j in range(1, min(idx, i) + 1):\n",
    "                if i == j or arr2[idx - j] > arr1[i - j - 1] :\n",
    "                    dp[i] = min(dp[i], (dp[i - j - 1] if i > j else 0) + j)\n",
    "        return dp[-1] if dp[-1] != float('inf') else - 1\n",
    "\n",
    "\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_right as br\r\n",
    "from functools import cache\r\n",
    "class Solution:\r\n",
    "    def makeArrayIncreasing(self, a: List[int], b: List[int]) -> int:\r\n",
    "        a.append(float('inf'))\r\n",
    "        b=sorted(list(set(b)))\r\n",
    "        c=[]\r\n",
    "        d=[]\r\n",
    "        for i in range(len(a)):\r\n",
    "            c.append(i-br(b,a[i]))\r\n",
    "            d.append(i-br(b,a[i]-1)-1)\r\n",
    "        # 记忆化搜索\r\n",
    "        @cache\r\n",
    "        def f(i):\r\n",
    "            if i==0:\r\n",
    "                return 1\r\n",
    "            tmp=-float('inf')\r\n",
    "            for j in range(i-1,-1,-1):\r\n",
    "                if a[j]<a[i] and c[j]>=d[i]:\r\n",
    "                    tmp=max(tmp,1+f(j))\r\n",
    "            # 全部替换\r\n",
    "            if d[i]<=-1:\r\n",
    "                tmp=max(tmp,1)\r\n",
    "            return tmp\r\n",
    "        ans=f(len(a)-1)\r\n",
    "        if ans==-float('inf'):\r\n",
    "            return -1\r\n",
    "        return len(a)-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_right as br\r\n",
    "from functools import cache\r\n",
    "class Solution:\r\n",
    "    def makeArrayIncreasing(self, a: List[int], b: List[int]) -> int:\r\n",
    "        # 替换次数最少时，最后一个数不一定不被替换，故加入inf以保证替换次数最少时最后一个数必定不被替换\r\n",
    "        a.append(float('inf'))\r\n",
    "        # 需要计数，故排序、去重\r\n",
    "        b=sorted(list(set(b)))\r\n",
    "        c=[]\r\n",
    "        d=[]\r\n",
    "        for i in range(len(a)):\r\n",
    "            c.append(i-br(b,a[i]))\r\n",
    "            d.append(i-br(b,a[i]-1)-1)\r\n",
    "        # 记忆化搜索\r\n",
    "        @cache\r\n",
    "        def f(i):\r\n",
    "            if i==0:\r\n",
    "                return 1\r\n",
    "            tmp=-float('inf')\r\n",
    "            for j in range(i-1,-1,-1):\r\n",
    "                # 替换(j,i)\r\n",
    "                if a[j]<a[i] and c[j]>=d[i]:\r\n",
    "                    tmp=max(tmp,1+f(j))\r\n",
    "            # 替换[0,i)\r\n",
    "            if d[i]<=-1:\r\n",
    "                tmp=max(tmp,1)\r\n",
    "            return tmp\r\n",
    "        ans=f(len(a)-1)\r\n",
    "        if ans==-float('inf'):\r\n",
    "            return -1\r\n",
    "        return len(a)-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        # 预处理\n",
    "        arr2 = sorted(set(arr2))\n",
    "        m, n = len(arr1), len(arr2)\n",
    "\n",
    "        # 1. dp数组下标及含义:\n",
    "        #   对arr1的前i个数进行了j次替换后，末尾的最小值\n",
    "        # 注意最多能替换的次数为min(m, n)\n",
    "        dp = [[float('inf')] * (min(m, n) + 1) for _ in range(m + 1)]\n",
    "\n",
    "        # 2. dp数组初始化: dp[0][0] = -1\n",
    "        dp[0][0] = -1\n",
    "\n",
    "        # 3. 递推表达式:\n",
    "        #   对于第i个数, 可以替换, 也可以不替换, 如果不替换:\n",
    "        #       dp[i][j] = min(dp[i][j], arr1[i]) \n",
    "        #   如果替换:\n",
    "        #       dp[i][j] = min(dp[i][j], arr2[k])\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(min(i, n) + 1):  # min(i, n)是味了防止下标越界\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]\n",
    "                if j and dp[i - 1][j - 1] != float('inf'):\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < n:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])\n",
    "                if i == m and dp[i][j] != float('inf'):\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n, m = len(arr1), len(arr2)\n",
    "        dp = [[inf] * (min(n, m) + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = -1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, m) + 1):\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])\n",
    "                if i == n and dp[i][j] != inf:\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        dp = [[inf] *(min(m, n)+1) for _ in range(n + 1)]\n",
    "        dp[0][0] = -1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, m) + 1):\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])\n",
    "                if i == n and dp[i][j] != inf:\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        dp = [[inf] *(min(m, n)+1) for _ in range(n + 1)]\n",
    "        dp[0][0] = -1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, m) + 1):\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])\n",
    "                if i == n and dp[i][j] != inf:\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        #这道题目前对我来说，主要的问题是，当不符合递增的时候，是替换前面的还是后面的\n",
    "        #我认为真的要分情况，前面后面都是可以的\n",
    "        #那我觉得就不太容易写了\n",
    "        #唉\n",
    "        #还有两个一起换，我服了\n",
    "\n",
    "        #抄了，太复杂了\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        dp = [[inf] *(min(m, n)+1) for _ in range(n + 1)]\n",
    "       # print(dp)\n",
    "        dp[0][0] = -1  #前i个元素替换j次，末尾的元素是\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, m) + 1):\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]   #不必替换\n",
    "                #这下面也太难懂了\n",
    "                #其实下面是和上面联系的\n",
    "                #该怎么做呢\n",
    "                #唉\n",
    "                #难崩\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])#保持末尾元素尽量小\n",
    "                if i == n and dp[i][j] != inf:#返回\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        # arr2 = sorted(set(arr2))\n",
    "        # n = len(arr1)\n",
    "        # m = len(arr2)\n",
    "        # dp = [[inf] *(min(m, n)+1) for _ in range(n + 1)]\n",
    "        # dp[0][0] = -1\n",
    "        # for i in range(1, n + 1):\n",
    "        #     for j in range(min(i, m) + 1):\n",
    "        #         if arr1[i - 1] > dp[i - 1][j]:\n",
    "        #             dp[i][j] = arr1[i - 1]\n",
    "        #         if j and dp[i - 1][j - 1] != inf:\n",
    "        #             k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "        #             if k < m:\n",
    "        #                 dp[i][j] = min(dp[i][j], arr2[k])\n",
    "        #         if i == n and dp[i][j] != inf:\n",
    "        #             return j\n",
    "        # return -1\n",
    "\n",
    "        nums1 = arr1\n",
    "        nums2 = arr2\n",
    "        nums2 = sorted(set(nums2))\n",
    "        m,n = len(nums1),len(nums2)\n",
    "        k = min(m,n)\n",
    "        dp = [[float('inf')]*(k+1) for _ in range(m)]\n",
    "        def minGt(t,l0):\n",
    "            l = l0\n",
    "            r = n-1\n",
    "            res = float('inf')\n",
    "            while l<=r:\n",
    "                mid = (l+r)//2\n",
    "                if nums2[mid]>t:\n",
    "                    res = nums2[mid]\n",
    "                    r = r-1\n",
    "                else:\n",
    "                    l = l+1\n",
    "            return res\n",
    "        dp[0][0] = nums1[0]\n",
    "        dp[0][1] = min(nums1[0],nums2[0])\n",
    "        for i in range(1,m):\n",
    "            for j in range(min(i+2,n+1)):\n",
    "                if dp[i-1][j]<nums1[i]:\n",
    "                    dp[i][j] = nums1[i]\n",
    "                # if j>0:\n",
    "                #     dp[i][j] = min(dp[i][j],minGt(dp[i-1][j-1],j-1))\n",
    "                if j>0 and dp[i - 1][j - 1] != float('inf'):\n",
    "                    k = bisect_right(nums2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k<n:\n",
    "                        dp[i][j] = min(dp[i][j],nums2[k])\n",
    "                if i==m-1 and dp[i][j]!=float('inf'):\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2=sorted(set(arr2))\n",
    "        n=len(arr1)\n",
    "        m=len(arr2)\n",
    "        dp=[[inf] *(min(m,n)+1) for _ in range(n+1)]\n",
    "        dp[0][0]=-1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(min(i,m)+1):\n",
    "                if arr1[i-1]>dp[i-1][j]:\n",
    "                    dp[i][j]=arr1[i-1]\n",
    "                if j and dp[i-1][j-1]!=inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])\n",
    "                if i == n and dp[i][j] != inf:\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        #这道题目前对我来说，主要的问题是，当不符合递增的时候，是替换前面的还是后面的\n",
    "        #我认为真的要分情况，前面后面都是可以的\n",
    "        #那我觉得就不太容易写了\n",
    "        #唉\n",
    "        #还有两个一起换，我服了\n",
    "\n",
    "        #抄了，太复杂了\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        dp = [[inf] *(min(m, n)+1) for _ in range(n + 1)]\n",
    "       # print(dp)\n",
    "        dp[0][0] = -1  #前i个元素替换j次，末尾的元素是\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, m) + 1):\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]   #不必替换\n",
    "                #这下面也太难懂了\n",
    "                #其实下面是和上面联系的\n",
    "                #该怎么做呢\n",
    "                #唉\n",
    "                #难崩\n",
    "\n",
    "                #其实很好理解，他就只能从这两个状态过来，上下两个，分别是换和不换\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])#保持末尾元素尽量小\n",
    "                if i == n and dp[i][j] != inf:#返回\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        dp = [[inf] *(min(m, n)+1) for _ in range(n + 1)]\n",
    "        dp[0][0] = -1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, m) + 1):\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])\n",
    "                if i == n and dp[i][j] != inf:\n",
    "                    return j\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        dp = [[inf] *(min(m, n)+1) for _ in range(n + 1)]\n",
    "        dp[0][0] = -1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, m) + 1):\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])\n",
    "                if i == n and dp[i][j] != inf:\n",
    "                    return j\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(set(arr2))\n",
    "        m,n = len(arr1),len(arr2)\n",
    "        dp = [[inf]*(n+1) for _ in range(m+1)]\n",
    "        dp[0][0] = -1\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(min(i, n) + 1):\n",
    "\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]\n",
    "\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < n:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])\n",
    "\n",
    "                if i == m and dp[i][j] != inf:\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        dp = [[inf] *(min(m, n)+1) for _ in range(n + 1)]\n",
    "        dp[0][0] = -1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, m) + 1):\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])\n",
    "                if i == n and dp[i][j] != inf:\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        #这道题目前对我来说，主要的问题是，当不符合递增的时候，是替换前面的还是后面的\n",
    "        #我认为真的要分情况，前面后面都是可以的\n",
    "        #那我觉得就不太容易写了\n",
    "        #唉\n",
    "        #还有两个一起换，我服了\n",
    "\n",
    "        #抄了，太复杂了\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        dp = [[inf] *(min(m, n)+1) for _ in range(n + 1)]\n",
    "       # print(dp)\n",
    "        dp[0][0] = -1  #前i个元素替换j次，末尾的元素是\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, m) + 1):\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]   #不必替换\n",
    "                #这下面也太难懂了\n",
    "                #其实下面是和上面联系的\n",
    "                #该怎么做呢\n",
    "                #唉\n",
    "                #难崩\n",
    "\n",
    "                #其实很好理解，他就只能从这两个状态过来，上下两个，分别是换和不换\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1])\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])#保持末尾元素尽量小\n",
    "                if i == n and dp[i][j] != inf:#返回\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        #这道题目前对我来说，主要的问题是，当不符合递增的时候，是替换前面的还是后面的\n",
    "        #我认为真的要分情况，前面后面都是可以的\n",
    "        #那我觉得就不太容易写了\n",
    "        #唉\n",
    "        #还有两个一起换，我服了\n",
    "\n",
    "        #抄了，太复杂了\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        dp = [[inf] *(min(m, n)+1) for _ in range(n + 1)]\n",
    "       # print(dp)\n",
    "        dp[0][0] = -1  #前i个元素替换j次，末尾的元素是\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, m) + 1):\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]   #不必替换\n",
    "                #这下面也太难懂了\n",
    "                #其实下面是和上面联系的\n",
    "                #该怎么做呢\n",
    "                #唉\n",
    "                #难崩\n",
    "\n",
    "                #其实很好理解，他就只能从这两个状态过来，上下两个，分别是不换和换\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1])\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])#保持末尾元素尽量小\n",
    "                if i == n and dp[i][j] != inf:#返回\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        # 预处理\n",
    "        arr2 = sorted(set(arr2))\n",
    "        m, n = len(arr1), len(arr2)\n",
    "\n",
    "        # 1. dp数组下标及含义:\n",
    "        #   对arr1的前i个数进行了j次替换后，末尾的最小值\n",
    "        # 注意最多能替换的次数为min(m, n)\n",
    "        dp = [[float('inf')] * (min(m, n) + 1) for _ in range(m + 1)]\n",
    "\n",
    "        # 2. dp数组初始化: dp[0][0] = -1\n",
    "        dp[0][0] = -1\n",
    "\n",
    "        # 3. 递推表达式:\n",
    "        #   对于第i个数, 可以替换, 也可以不替换, 如果不替换:\n",
    "        #       dp[i][j] = min(dp[i][j], arr1[i]) \n",
    "        #   如果替换:\n",
    "        #       dp[i][j] = min(dp[i][j], arr2[k])\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(min(i, n) + 1):  # min(i, n)是味了防止下标越界\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]\n",
    "                if j and dp[i - 1][j - 1] != float('inf'):\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1])\n",
    "                    if k < n:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])\n",
    "                if i == m and dp[i][j] != float('inf'):\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(set(arr2))\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        dp = [[inf] *(min(m, n)+1) for _ in range(n + 1)]\n",
    "        dp[0][0] = -1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, m) + 1):\n",
    "                if arr1[i - 1] > dp[i - 1][j]:\n",
    "                    dp[i][j] = arr1[i - 1]\n",
    "                if j and dp[i - 1][j - 1] != inf:\n",
    "                    k = bisect_right(arr2, dp[i - 1][j - 1], j - 1)\n",
    "                    if k < m:\n",
    "                        dp[i][j] = min(dp[i][j], arr2[k])\n",
    "                if i == n and dp[i][j] != inf:\n",
    "                    return j\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2.sort()\n",
    "        n,m=len(arr1),len(arr2)\n",
    "        dp=[[float('inf')]*(m+1) for _ in range(n+1)]\n",
    "        dp[0][0]=-1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(m+1):\n",
    "                if arr1[i-1]>dp[i-1][j]:\n",
    "                    dp[i][j]=arr1[i-1]\n",
    "                if j>0 and dp[i-1][j-1]!=float('inf'):\n",
    "                    k=bisect_right(arr2,dp[i-1][j-1])\n",
    "                    if k<m:\n",
    "                    \tdp[i][j]=min(dp[i][j],arr2[k])\n",
    "                if i==n and dp[i][j]!=float('inf'):\n",
    "                    return j\n",
    "        return -1\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = list(set(arr2))\n",
    "        arr2.sort()\n",
    "        m,n = len(arr1),len(arr2)\n",
    "        arr1 = [-inf] + arr1\n",
    "        import bisect\n",
    "        dp = [[inf]*(1+min(m,n)) for _ in range(m+1)]\n",
    "        dp[0][0] = -inf\n",
    "        print(arr1,arr2)\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(min(m,n)+1):\n",
    "                if arr1[i] >  dp[i-1][j]:\n",
    "                    dp[i][j] = arr1[i]\n",
    "                if j>0:\n",
    "                    pos = bisect.bisect_right(arr2,dp[i-1][j-1])\n",
    "                    if pos < n:\n",
    "                        dp[i][j] = min(dp[i][j],arr2[pos])\n",
    "                if i == m and dp[i][j] != inf:\n",
    "                    return j\n",
    "            #print(dp[i])\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    INT_MAX = sys.maxsize\n",
    "\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        \"\"\"dp[i][k]表示：如果我们可以使用k次替换操作使得前i个元素严格递增，此时第i个元素可以选择的最小值。\"\"\"\n",
    "        arr2.sort()\n",
    "\n",
    "        n = len(arr1)\n",
    "        dp = [[self.INT_MAX for _ in range(n + 1)] for _ in range(n)]\n",
    "        for k in range(n + 1):\n",
    "            dp[0][k] = arr2[0] if k > 0 else arr1[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for k in range(n + 1):\n",
    "                # arr1[i] don't do the assignment\n",
    "                if arr1[i] > dp[i - 1][k]:\n",
    "                    dp[i][k] = arr1[i]\n",
    "\n",
    "                # arr1[i] do the assignment\n",
    "                if k < 1: continue\n",
    "                r_idx = bisect.bisect_right(arr2, dp[i - 1][k - 1])\n",
    "                if r_idx < len(arr2):\n",
    "                    dp[i][k] = min(dp[i][k], arr2[r_idx])\n",
    "\n",
    "        for k in range(n + 1):\n",
    "            if dp[n - 1][k] != self.INT_MAX:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_right\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        # 动态规划\n",
    "        arr2=sorted(set(arr2))\n",
    "        n1=len(arr1)\n",
    "        n2=len(arr2)\n",
    "        dp=[[2147483647 for _ in range(min(n1,n2)+1)] for _ in range(n1+1)]\n",
    "        dp[0][0]=-1\n",
    "        for i in range(1,n1+1):\n",
    "            for j in range(min(i,n2)+1):\n",
    "                if arr1[i-1]>dp[i-1][j]:\n",
    "                    dp[i][j]=arr1[i-1]\n",
    "                if j!=0 and dp[i-1][j-1]!=2147483647:\n",
    "                    k=bisect_right(arr2,dp[i-1][j-1],j-1)\n",
    "                    if k<n2:\n",
    "                        dp[i][j]=min(dp[i][j],arr2[k])\n",
    "                if i==n1 and dp[i][j]!=2147483647:\n",
    "                    return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2.sort()\n",
    "        arr2Ptr = 0\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        k = min(m,n)\n",
    "        self.ret = inf\n",
    "        def bs(left, target):\n",
    "            right = n-1\n",
    "            while left + 1 < right:\n",
    "                mid = (left+right)//2\n",
    "                if arr2[mid] <= target:\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            if left < n and arr2[left] > target: return left\n",
    "            if right < n and arr2[right] > target: return right\n",
    "            return n\n",
    "        dp = [[inf for _ in range(k+1)] for _ in range(m)]\n",
    "        dp[0][0] = arr1[0]\n",
    "        dp[0][1] = arr2[0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(k):\n",
    "                if dp[i-1][j] < arr1[i]:\n",
    "                    dp[i][j] = min(dp[i][j], arr1[i])\n",
    "                if j != k:\n",
    "                    num2Ptr = bs(0, dp[i-1][j])\n",
    "                    if num2Ptr < n:\n",
    "                        dp[i][j+1] = min(dp[i][j+1], arr2[num2Ptr])\n",
    "        for j in range(k+1):\n",
    "            if dp[-1][j] != inf:\n",
    "                return j\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        if len(arr1) == 1: return 0\n",
    "        l = sorted(list(arr2))\n",
    "        N = len(arr1) + 1\n",
    "        @cache\n",
    "        def dfs(i, lst):\n",
    "            if i == len(arr1):\n",
    "                return 0\n",
    "            r = N\n",
    "            if lst < arr1[i]:\n",
    "                r = min(r, dfs(i + 1, arr1[i]))\n",
    "            j = bisect_right(l, lst)\n",
    "            if j < len(l):\n",
    "                r = min(r, dfs(i + 1, l[j]) + 1)\n",
    "            return r\n",
    "        \n",
    "        res = dfs(0, -1)\n",
    "        dfs.cache_clear()\n",
    "        return res if res < N else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n,m = len(arr1),len(arr2)\n",
    "        arr2.sort()\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            if arr1[i] > pre:\n",
    "                ans = dfs(i + 1,arr1[i])\n",
    "            idx = bisect_right(arr2,pre)\n",
    "            if idx < m:\n",
    "                if arr2[idx] >= arr1[i] > pre:\n",
    "                    return ans\n",
    "                ans = min(ans,dfs(i + 1,arr2[idx]) + 1)\n",
    "            return ans\n",
    "        \n",
    "        ans = dfs(0,-inf)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, a: List[int], b: List[int]) -> int:\n",
    "        b = list(set(b))\n",
    "        b.sort()  # 为能二分查找，对 b 排序\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int, pre: int) -> int:\n",
    "            if i < 0: return 0\n",
    "            res = dfs(i - 1, a[i]) if a[i] < pre else inf  # 不替换 a[i]\n",
    "            k = bisect_left(b, pre) - 1  # 二分查找 b 中小于 pre 的最大数的下标\n",
    "            if k >= 0:  # a[i] 替换成小于 pre 的最大数\n",
    "                res = min(res, dfs(i - 1, b[k]) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(a) - 1, inf)  # 假设 a[n-1] 右侧有个无穷大的数\n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        # 数组2中的元素赋值到数组1，使得数组1递增的最少操作数：\n",
    "\n",
    "        # 1. 递归\n",
    "        arr2.sort() # 便于二分\n",
    "        @cache\n",
    "        def dfs(i:int, pre:int) -> int:\n",
    "            if i < 0: return 0 \n",
    "            res = dfs(i - 1, arr1[i]) if arr1[i] < pre else inf # 不替换a[i]\n",
    "            k = bisect_left(arr2, pre) - 1 # \n",
    "            if k >= 0: # a[i]替换成小于pre的最大数\n",
    "                res = min(res, dfs(i - 1, arr2[k]) + 1)\n",
    "            return res \n",
    "        ans = dfs(len(arr1) - 1, inf) # 假设a[n-1]右侧有无穷大的数\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        b=arr2\n",
    "        a=arr1\n",
    "        b.sort()  # 为能二分查找，对 b 排序\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int, pre: int) -> int:\n",
    "            if i < 0: return 0\n",
    "            res = dfs(i - 1, a[i]) if a[i] < pre else inf  # 不替换 a[i]\n",
    "            k = bisect_left(b, pre) - 1  # 二分查找 b 中小于 pre 的最大数的下标\n",
    "            if k >= 0:  # a[i] 替换成小于 pre 的最大数\n",
    "                res = min(res, dfs(i - 1, b[k]) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(a) - 1, inf)  # 假设 a[n-1] 右侧有个无穷大的数\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2.sort() # 为能二分查找对arr2排序\n",
    "\n",
    "        @cache\n",
    "        def dfs(i:int, pre:int) -> int:\n",
    "            if i < 0: return 0\n",
    "            res = dfs(i - 1 , arr1[i]) if arr1[i] < pre else inf #不替换a[i]\n",
    "            k = bisect_left(arr2, pre) - 1 #二分查找b中小于pre的最大数的下标\n",
    "            if k >= 0: # a[i]替换成小于pre的最大数\n",
    "                res = min(res, dfs(i - 1, arr2[k]) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(arr1) - 1, inf) #假设a[n - 1]右侧有个无穷大的数\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(arr2)\n",
    "        n = len(arr1)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, pre):\n",
    "            if i < 0: return 0\n",
    "            if arr1[i] < pre:\n",
    "                res = dfs(i-1, arr1[i])\n",
    "            else: res = inf\n",
    "            k = bisect_left(arr2, pre) - 1\n",
    "            return min(res, dfs(i-1, arr2[k]) + 1) if k >= 0 else res\n",
    "\n",
    "        ans = dfs(n - 1, inf)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, a: List[int], b: List[int]) -> int:\n",
    "        b.sort()  # 为能二分查找，对 b 排序\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int, pre: int) -> int:\n",
    "            if i < 0: return 0\n",
    "            res = dfs(i - 1, a[i]) if a[i] < pre else inf  # 不替换 a[i]\n",
    "            k = bisect_left(b, pre) - 1  # 二分查找 b 中小于 pre 的最大数的下标\n",
    "            if k >= 0:  # a[i] 替换成小于 pre 的最大数\n",
    "                res = min(res, dfs(i - 1, b[k]) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(a) - 1, inf)  # 假设 a[n-1] 右侧有个无穷大的数\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, a: List[int], b: List[int]) -> int:\n",
    "        b.sort()\n",
    "        @cache\n",
    "        def dfs(i, pre):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            res = dfs(i-1, a[i]) if a[i] < pre else inf\n",
    "            k = bisect.bisect_left(b, pre) - 1\n",
    "            if k >= 0:\n",
    "                res = min(res, dfs(i - 1, b[k]) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(a) - 1, inf)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, a: List[int], b: List[int]) -> int:\n",
    "        b.sort()  # 为能二分查找，对 b 排序\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int, pre: int) -> int:\n",
    "            if i < 0: return 0\n",
    "            res = dfs(i - 1, a[i]) if a[i] < pre else inf  # 不替换 a[i]\n",
    "            k = bisect_left(b, pre) - 1  # 二分查找 b 中小于 pre 的最大数的下标\n",
    "            if k >= 0:  # a[i] 替换成小于 pre 的最大数\n",
    "                res = min(res, dfs(i - 1, b[k]) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(a) - 1, inf)  # 假设 a[n-1] 右侧有个无穷大的数\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/make-array-strictly-increasing/solutions/2236095/zui-chang-di-zeng-zi-xu-lie-de-bian-xing-jhgg/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        a = arr1\n",
    "        b = arr2\n",
    "        b.sort()  # 为能二分查找，对b排序\n",
    "        @cache  # 缓存装饰器，避免重复\n",
    "        def dfs(i, pre):\n",
    "            if i < 0: return 0\n",
    "            res = dfs(i - 1, a[i]) if a[i] < pre else inf\n",
    "            k = bisect_left(b, pre) - 1\n",
    "            if k >= 0:\n",
    "                res = min(res, dfs(i - 1, b[k]) + 1)\n",
    "            return res\n",
    "\n",
    "        ans = dfs(len(a) - 1, inf)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "       arr2.sort()\n",
    "       n=len(arr1)\n",
    "       @cache\n",
    "       def g(i,p):\n",
    "          if i<0:\n",
    "             return 0\n",
    "          res=g(i-1,arr1[i]) if arr1[i]<p else inf\n",
    "          k=bisect_left(arr2,p)-1\n",
    "          if k>=0:\n",
    "             res=min(res,g(i-1,arr2[k])+1)\n",
    "          return res\n",
    "       return g(n-1,inf) if g(n-1,inf)<inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        a = arr1\n",
    "        b = arr2\n",
    "        b.sort()  # 为能二分查找，对b排序\n",
    "        @cache  # 缓存装饰器，避免重复\n",
    "        def dfs(i, pre):\n",
    "            if i < 0: return 0\n",
    "            res = dfs(i - 1, a[i]) if a[i] < pre else inf\n",
    "            k = bisect_left(b, pre) - 1\n",
    "            if k >= 0:\n",
    "                res = min(res, dfs(i - 1, b[k]) + 1)\n",
    "            return res\n",
    "\n",
    "        ans = dfs(len(a) - 1, inf)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2.sort()\n",
    "        @cache\n",
    "        def dfs(i, pre):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            res = dfs(i - 1, arr1[i]) if arr1[i] < pre else math.inf\n",
    "            k = bisect.bisect_left(arr2, pre) - 1\n",
    "            if k >= 0:\n",
    "                res = min(res, dfs(i - 1, arr2[k]) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(arr1) - 1, math.inf)\n",
    "        return ans if ans < math.inf else -1\n",
    "\n",
    "        \"\"\"\n",
    "        arr2.sort()\n",
    "        print(arr2)\n",
    "\n",
    "        def helper(minval, maxval):\n",
    "            # find the smallest arr2[i] between (minval, maxval)\n",
    "            nonlocal arr2\n",
    "            left, right = 0, len(arr2) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if arr2[mid] <= minval:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if left == len(arr2) or arr2[left] >= maxval:\n",
    "                return -1\n",
    "            else:\n",
    "                return left\n",
    "        cnt = 0\n",
    "        for i in range(len(arr1) - 1):\n",
    "            if arr1[i + 1] <= arr1[i]:\n",
    "                idx = None\n",
    "                if i == 0:\n",
    "                    idx = helper(-1, arr1[1])\n",
    "                else:\n",
    "                    idx = helper(arr1[i - 1], arr1[i + 1])\n",
    "                if idx != -1:\n",
    "                    print(i, 'of arr1: ', arr1[i], 'to ', idx, 'of arr2:', arr2[idx])\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    idx = helper(arr1[i], math.inf)\n",
    "                    if idx != -1:\n",
    "                        arr1[i + 1] = arr2[idx]\n",
    "                        print(i + 1, 'of arr1: ', arr1[i + 1], 'to ', idx, 'of arr2:', arr2[idx])\n",
    "                        cnt += 1\n",
    "                    else:\n",
    "                        idx = helper(arr1[i - 1], math.inf if i + 2 == len(arr1) else arr1[i + 2])\n",
    "                        if idx == len(arr2) - 1:\n",
    "                            return -1\n",
    "                        if i + 2 < len(arr1) and arr2[idx + 1] >= arr1[i + 2]:\n",
    "                            return -1\n",
    "                        arr1[i], arr1[i + 1] = arr2[idx], arr2[idx + 1]\n",
    "                        cnt += 2\n",
    "        return cnt\n",
    "        \"\"\"\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2.sort()\n",
    "        @cache\n",
    "        def dfs(i: int, pre: int) -> int:\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            ans = dfs(i - 1, arr1[i]) if arr1[i] < pre else inf\n",
    "            k = bisect_left(arr2, pre) - 1\n",
    "            if k >= 0:\n",
    "                ans = min(ans, dfs(i - 1, arr2[k]) + 1)\n",
    "            return ans\n",
    "        ans = dfs(len(arr1) - 1, inf)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, a: List[int], b: List[int]) -> int:\n",
    "        b.sort()  # 为能二分查找，对 b 排序\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int, pre: int) -> int:\n",
    "            if i < 0: return 0\n",
    "            res = dfs(i - 1, a[i]) if a[i] < pre else inf  # 不替换 a[i]\n",
    "            k = bisect_left(b, pre) - 1  # 二分查找 b 中小于 pre 的最大数的下标\n",
    "            if k >= 0:  # a[i] 替换成小于 pre 的最大数\n",
    "                res = min(res, dfs(i - 1, b[k]) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(a) - 1, inf)  # 假设 a[n-1] 右侧有个无穷大的数\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2.sort()\n",
    "        @cache\n",
    "        def dfs(i, next):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            res = dfs(i - 1, arr1[i]) if arr1[i] < next else inf\n",
    "            j = bisect_left(arr2, next) - 1\n",
    "            if j >= 0:\n",
    "                res = min(res, dfs(i - 1, arr2[j]) + 1)\n",
    "            return res\n",
    "        res = dfs(len(arr1) - 1, inf)\n",
    "        return res if res != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2.sort()\n",
    "        @cache\n",
    "        def dfs(i:int,pre:int)->int:\n",
    "            if i<0:return 0\n",
    "            res=dfs(i-1,arr1[i]) if arr1[i]<pre else inf\n",
    "            k=bisect_left(arr2,pre)-1\n",
    "            if k>=0:\n",
    "                res=min(res,dfs(i-1,arr2[k])+1)\n",
    "            return res\n",
    "        ans=dfs(len(arr1)-1,inf)\n",
    "        return ans if ans <inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = list(set(arr2))\n",
    "        arr2.sort()\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i == len(arr1):\n",
    "                return 0\n",
    "            j = bisect_right(arr2,pre)\n",
    "            ans = inf\n",
    "            if j < len(arr2):\n",
    "                ans = min(ans,1 + dfs(i + 1,arr2[j]))\n",
    "            if pre < arr1[i]:\n",
    "                ans = min(ans,dfs(i + 1,arr1[i]))\n",
    "            return ans\n",
    "        ans = dfs(0,-inf)\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2.sort()\n",
    "        @cache\n",
    "        def dfs(i,p):\n",
    "            if i == len(arr1): return 0\n",
    "            a = inf\n",
    "            if arr1[i]>p:a=min(a,dfs(i+1,arr1[i]))\n",
    "            idx = bisect_left(arr2,p+1)\n",
    "            if idx < len(arr2):\n",
    "                a = min(a,dfs(i+1,arr2[idx])+1)\n",
    "            return a\n",
    "        r = dfs(0,-1)\n",
    "        return r if r<inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n,m = len(arr1),len(arr2)\n",
    "        arr2.sort()\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            if arr1[i] > pre:\n",
    "                ans = dfs(i + 1,arr1[i])\n",
    "            idx = bisect_right(arr2,pre)\n",
    "            if idx < m:\n",
    "                ans = min(ans,dfs(i + 1,arr2[idx]) + 1)\n",
    "            return ans\n",
    "        \n",
    "        ans = dfs(0,-inf)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        # 记忆化搜索\n",
    "        @cache\n",
    "        def dfs(pre:int,pos:int):\n",
    "            if pos == n:\n",
    "                return 0\n",
    "            cur = arr1[pos]\n",
    "            ans = sys.maxsize \n",
    "            # 可以不换\n",
    "            if cur > pre:\n",
    "                ans = dfs(cur,pos+1)\n",
    "            # 换\n",
    "            idx = bisect.bisect(arr2,pre)\n",
    "            if idx<m:\n",
    "                tmp = dfs(arr2[idx],pos+1)\n",
    "                if tmp != sys.maxsize:\n",
    "                    ans = min(ans,tmp+1)\n",
    "            return ans\n",
    "\n",
    "        list.sort(arr2)\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        ans = dfs(-1,0)\n",
    "        return -1 if ans == sys.maxsize else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n,m = len(arr1),len(arr2)\n",
    "        arr2.sort()\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            if arr1[i] > pre:\n",
    "                ans = dfs(i + 1,arr1[i])\n",
    "            idx = bisect_right(arr2,pre)\n",
    "            if idx < m :\n",
    "                ans = min(ans,dfs(i + 1,arr2[idx]) + 1)\n",
    "            return ans\n",
    "        \n",
    "        ans = dfs(0,-inf)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        arr2.sort()\n",
    "        \n",
    "        rec = defaultdict(lambda:-1)\n",
    "        def dfs(i, pre):\n",
    "            # dfs(i, pre)表示将数组arr1[:i+1]这段替换为严格递增且最后一个数小于pre的最小操作数\n",
    "            # 选择是否替换当前的arr[i], 有两种情况（换与不换）\n",
    "            if i==-1: return 0\n",
    "            if rec[(i,pre)]!=-1:\n",
    "                return rec[(i,pre)]\n",
    "            res = float('inf')\n",
    "            if arr1[i]<pre:\n",
    "                res = min(res, dfs(i-1, arr1[i]))    # 第一种，如果arr1[i]小于pre，可以不替换当前的arr1[i]\n",
    "            idx = bisect_left(arr2, pre)      #第二种，在arr2中找小于pre的最大的数，替换arr1[i]\n",
    "            if idx>0:\n",
    "                res = min(res, dfs(i-1, arr2[idx-1])+1)\n",
    "            rec[(i,pre)] = res\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(n-1, float('inf'))\n",
    "        return ans if ans<float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        arr2.sort()\n",
    "        \n",
    "        rec = defaultdict(lambda:-1)\n",
    "        def dfs(i, pre):\n",
    "            # dfs(i, pre)表示将数组arr1[:i+1]这段替换为严格递增且最后一个数小于pre的最小操作数\n",
    "            if i==-1: return 0\n",
    "            if rec[(i,pre)]!=-1:\n",
    "                return rec[(i,pre)]\n",
    "            res = float('inf')\n",
    "            if arr1[i]<pre:\n",
    "                res = min(res, dfs(i-1, arr1[i]))    # arr1[i]小于pre，可以不替换当前的arr1[i]\n",
    "            idx = bisect_left(arr2, pre)      #在arr2中找小于pre的最大的数，替换arr1[i]\n",
    "            if idx>0:\n",
    "                res = min(res, dfs(i-1, arr2[idx-1])+1)\n",
    "            rec[(i,pre)] = res\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(n-1, float('inf'))\n",
    "        return ans if ans<float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_right as br\r\n",
    "from functools import cache\r\n",
    "class Solution:\r\n",
    "    def makeArrayIncreasing(self, a: List[int], b: List[int]) -> int:\r\n",
    "        b=sorted(b)\r\n",
    "        @cache\r\n",
    "        def f(i,pre):\r\n",
    "            if i==len(a):\r\n",
    "                return 0\r\n",
    "            tmp=float('inf')\r\n",
    "            if a[i]>pre:\r\n",
    "                # i>pre,可以不替换a[i]\r\n",
    "                tmp=f(i+1,a[i])\r\n",
    "            if b[-1]>pre:\r\n",
    "                # b中存在大于pre的数，用最小的大于pre的数替换\r\n",
    "                tmp=min(tmp,f(i+1,b[br(b,pre)])+1)\r\n",
    "            return tmp\r\n",
    "        ans=f(0,-1)\r\n",
    "        if ans==float('inf'):\r\n",
    "            return -1\r\n",
    "        else:\r\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        arr2.sort()\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, pre):\n",
    "            # dfs(i, pre)表示将数组arr1[:i+1]这段替换为严格递增且最后一个数小于pre的最小操作数\n",
    "            if i==-1: return 0\n",
    "            res = float('inf')\n",
    "            if arr1[i]<pre:\n",
    "                res = min(res, dfs(i-1, arr1[i]))    # arr1[i]小于pre，可以不替换当前的arr1[i]\n",
    "            idx = bisect_left(arr2, pre)      #在arr2中找小于pre的最大的数，替换arr1[i]\n",
    "            if idx>0:\n",
    "                res = min(res, dfs(i-1, arr2[idx-1])+1)\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(n-1, float('inf'))\n",
    "        return ans if ans<float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = list(set(arr2))\n",
    "        arr2.sort()\n",
    "        @cache\n",
    "        def search(at, ban):\n",
    "            if at == len(arr1): return 0\n",
    "            if at > 0 and arr1[at] <= ban:\n",
    "                jump = bisect.bisect_right(arr2, ban)\n",
    "                if jump == len(arr2): return 99999\n",
    "                return search(at+1, arr2[jump])+1\n",
    "            elif at == 0:\n",
    "                return min(search(at+1, arr1[0]), search(at+1, arr2[0])+1)\n",
    "            else:\n",
    "                jump = bisect.bisect_right(arr2, ban)\n",
    "                if jump == len(arr2): return search(at+1, arr1[at])\n",
    "                return min(search(at+1, arr2[jump])+1, search(at+1, arr1[at]))\n",
    "        ans = search(0,0)\n",
    "        if ans < 99999: return ans\n",
    "        else: return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = [k for k in Counter(arr2)]\n",
    "        m, n = len(arr1), len(arr2) \n",
    "        arr2.sort() \n",
    "        #print(arr2) \n",
    "        dp = [[float('inf')] * (n+1) for _ in range(m)]\n",
    "        dp[0][0] = 0 \n",
    "        for i in range(1, n+1):\n",
    "            dp[0][i] = 1\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n+1):\n",
    "                if j > 1:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                if arr2[j-1] > arr1[i-1]:\n",
    "                    dp[i][j]= min(dp[i][j], dp[i-1][0] + 1) \n",
    "            if arr1[i] > arr1[i-1]:\n",
    "                dp[i][0] = dp[i-1][0] \n",
    "            j = bisect.bisect_left(arr2, arr1[i]) - 1\n",
    "            if j >= 0:\n",
    "                dp[i][0] = min(dp[i][0], dp[i-1][j+1]) \n",
    "        ans = min(dp[m-1])\n",
    "        return ans if ans < float('inf') else -1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2.sort()\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, pre: int) -> int:\n",
    "            if i == len(arr1): return 0\n",
    "            res = inf\n",
    "            # 换\n",
    "            pos = bisect_right(arr2, pre)\n",
    "            if pos < len(arr2):\n",
    "                res = dfs(i + 1, arr2[pos]) + 1\n",
    "\n",
    "            # 不换\n",
    "            if arr1[i] > pre:\n",
    "                res = min(res, dfs(i + 1, arr1[i]))\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(0, -1)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(list(set(arr2)))\n",
    "\n",
    "        @lru_cache\n",
    "        def upper_bound(pre: int) -> int:\n",
    "            return bisect_right(arr2, pre)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, pre: int) -> int:\n",
    "            if i == len(arr1):return 0\n",
    "            op = inf\n",
    "            ans = upper_bound(pre)\n",
    "            if ans != len(arr2):\n",
    "                op = dfs(i + 1, arr2[ans]) + 1\n",
    "            if arr1[i] > pre:\n",
    "                op = min(op, dfs(i + 1, arr1[i]))\n",
    "            return op\n",
    "\n",
    "        tmp = dfs(0, -1)\n",
    "        return tmp if tmp != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        arr2 = sorted(list(set(arr2)))\n",
    "\n",
    "        @cache\n",
    "        def upper_bound(pre: int) -> int:\n",
    "            return bisect_right(arr2, pre)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, pre: int) -> int:\n",
    "            if i == len(arr1):return 0\n",
    "            op = inf\n",
    "            ans = upper_bound(pre)\n",
    "            if ans != len(arr2):\n",
    "                op = dfs(i + 1, arr2[ans]) + 1\n",
    "            if arr1[i] > pre:\n",
    "                op = min(op, dfs(i + 1, arr1[i]))\n",
    "            return op\n",
    "\n",
    "        tmp = dfs(0, -1)\n",
    "        return tmp if tmp != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        m,n = len(arr1),len(arr2)\n",
    "        arr2.sort()\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i == m:\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return min(dfs(i + 1,pre),dfs(i + 1,0) + 1)\n",
    "            ans = inf\n",
    "            if pre == -1:\n",
    "                if arr1[i] > arr1[i - 1]:\n",
    "                    ans = dfs(i + 1,-1)\n",
    "                idx = bisect_right(arr2,arr1[i - 1])# 找比前一个数大的最小的数\n",
    "                if idx < n:\n",
    "                    ans = min(ans,dfs(i + 1,idx) + 1)\n",
    "            else:\n",
    "                if arr1[i] > arr2[pre]:\n",
    "                    ans = dfs(i + 1,-1)\n",
    "                idx = bisect_right(arr2,arr2[pre])# 找比前一个数大的最小的数\n",
    "                if idx < n:\n",
    "                    ans = min(ans,dfs(i + 1,idx) + 1)\n",
    "            return ans\n",
    "        return dfs(0,-1) if dfs(0,-1) < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        m,n = len(arr1),len(arr2)\n",
    "        arr2.sort()\n",
    "        # pre==-1代表上一个元素是i - 1,否则是arr2[pre]\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i == m:\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return min(dfs(i + 1,pre),dfs(i + 1,0) + 1)\n",
    "            ans = inf\n",
    "            if pre == -1:\n",
    "                if arr1[i] > arr1[i - 1]:\n",
    "                    ans = dfs(i + 1,-1)\n",
    "                idx = bisect_right(arr2,arr1[i - 1])# 找比前一个数大的最小的数\n",
    "                if idx < n:\n",
    "                    ans = min(ans,dfs(i + 1,idx) + 1)\n",
    "            else:\n",
    "                if arr1[i] > arr2[pre]:\n",
    "                    ans = dfs(i + 1,-1)\n",
    "                idx = bisect_right(arr2,arr2[pre])# 找比前一个数大的最小的数 \n",
    "                if idx < n:\n",
    "                    ans = min(ans,dfs(i + 1,idx) + 1)\n",
    "            return ans\n",
    "        return dfs(0,-1) if dfs(0,-1) < inf else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
